/*
 * @Author: Starfish_DL
 * @Date: 2020-09-28 20:31:05
 * @LastEditors: Starfish_DL
 * @LastEditTime: 2020-09-29 11:53:42
 * @CurrentVersion: 1.0
 * @Description: 
 */

#include<iostream>
#include<string>
using namespace std;

class cLinkStackNode
{
public:
    char data;
    cLinkStackNode *next;
    cLinkStackNode();
    ~cLinkStackNode();
};

cLinkStackNode::cLinkStackNode()
{
    data='0';
    next=nullptr;
}

cLinkStackNode::~cLinkStackNode()
{
}

class cLinkStack
{
public:
    cLinkStackNode *s;
    cLinkStack();
    void Push(char e);
    char Pop();
    bool isEmpty();
    char getTop();
    ~cLinkStack();
};

cLinkStack::cLinkStack()
{
    s=new cLinkStackNode();
}

cLinkStack::~cLinkStack()
{
    delete s;
}

void cLinkStack::Push(char e)
{
    cLinkStackNode *n=new cLinkStackNode();
    n->data=e;
    n->next=s->next;
    s->next=n;
}

char cLinkStack::Pop()
{
    if (s->next==nullptr)
    {
        return '0';
    }
    cLinkStackNode *p=s->next;
    s->next=p->next;
    char temp=p->data;
    delete p;
    return temp;
}

bool cLinkStack::isEmpty()
{
    return (s->next==nullptr);
}

char cLinkStack::getTop()
{
    if (s->next==nullptr)
    {
        return '0';
    }
    return (s->next->data);
}

class iStackLinkNode
{
public:
    int data;
    iStackLinkNode *next;
    iStackLinkNode(/* args */);
    ~iStackLinkNode();
};

iStackLinkNode::iStackLinkNode()
{
    data=0;
    next=nullptr;
}

iStackLinkNode::~iStackLinkNode()
{
}

class iStackLink
{
    //done the class of linkstack has finished.
public:
    iStackLinkNode *s;
    iStackLink(/* args */);
    void Push(int e);
    int Pop();
    int GetTop();
    bool isEmpty();
    ~iStackLink();
};

iStackLink::iStackLink()
{
    s=new iStackLinkNode();
}

iStackLink::~iStackLink()
{
    iStackLinkNode *pre=s->next,*p=s;
    while (pre!=nullptr)
    {
        delete p;
        p=pre;
        pre=pre->next;
    }
    delete p;
}

void iStackLink::Push(int e)
{
    //done function of pushing has finished.
    iStackLinkNode *pre=new iStackLinkNode();
    pre->next=s->next;
    s->next=pre;
    pre->data=e;
}

int iStackLink::Pop()
{
    iStackLinkNode *p=s->next;
    int e=p->data;
    s->next=p->next;
    delete p;
    return e;
}

int iStackLink::GetTop()
{
    return (s->next->data);
}

bool iStackLink::isEmpty()
{
    return (s->next==nullptr);
}

string trans(string exp)
{
    //done 此函数已经顺利完成！
    string result;
    cLinkStack *postexp=new cLinkStack();
    for (int i = 0; i < exp.length(); i++)
    {
        //cout<<1<<endl;
        switch (exp[i])
        {
        case '+':
        case '-':
            if (postexp->getTop()=='(')
            {
                postexp->Push(exp[i]);
            }
            else
            {
                while (postexp->isEmpty()==false)
                {
                    result.insert(result.length(),1,postexp->Pop());
                    //note insert关于char类型的重载是有3个参数，其中第二个参数就是char数据的重复次数;
                }
                postexp->Push(exp[i]);
            }
            break;
        case '*':
        case '/':
            if (postexp->getTop()=='(')
            {
                postexp->Push(exp[i]);
            }
            else
            {
                while (postexp->getTop()=='*' || postexp->getTop()=='/')
                {
                    result.insert(result.length(),1,postexp->Pop());
                }
                postexp->Push(exp[i]);
            }
            break;
        case '(':
            postexp->Push(exp[i]);
            break;
        case ')':
            while (postexp->getTop()!='(')
            {
                result.insert(result.length(),1,postexp->Pop());
            }
            postexp->Pop();
            break;
        default:
            while (exp[i]>='0' && exp[i]<='9')
            {
                result.insert(result.length(),1,exp[i]);
                i++;                
            }
            result.insert(result.length()," "); 
            i--;           
            break;
        }
    }
    while (postexp->isEmpty()==false)
    {
        result.insert(result.length(),1,postexp->Pop());
    }
    delete postexp;
    return result;
}

//note 这里涉及到的表达式原理要掌握！

int compvalue(string exp)
{
    //done 已经完成后缀表达式求值函数！
    iStackLink *postexp=new iStackLink();
    int behind=0,front=0,result=0;
    for (int i = 0; i < exp.length(); i++)
    {
        switch (exp[i])
        {
        case '+':
            behind=postexp->Pop();
            front=postexp->Pop();
            result=behind+front;
            postexp->Push(result);
            break;
        case '-':
            behind=postexp->Pop();
            front=postexp->Pop();
            result=front-behind;
            postexp->Push(result);
            break;
        case '*':
            behind=postexp->Pop();
            front=postexp->Pop();
            result=behind*front;
            postexp->Push(result);
            break;
        case '/':
            behind=postexp->Pop();
            front=postexp->Pop();
            result=front/behind;
            postexp->Push(result);
            break;
        default:
            if (exp[i]==' ')
            {
                break;
            }
            else
            {
                string sTemp;
                while (exp[i]>='0' && exp[i]<='9')
                {
                    sTemp.insert(sTemp.length(),1,exp[i]);
                    i++;
                }
                int iTemp=stoi(sTemp,0,10);
                postexp->Push(iTemp);
                i--;
                break;
            }
        }
    }
    int answer=postexp->GetTop();
    delete postexp;
    return answer;
}

int main(/* int argc, char const *argv[] */)
{
    //string str1="177+3*(51-6)/44";
    //cout<<trans(str1)<<endl;
    string str2="(177+3)*4/3";
    cout<<compvalue(trans(str2))<<endl;
    return 0;
}
